package com.zk.algorithm.dynamicprogramming;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.Hard;
import com.zk.algorithm.annotation.LeetCode;

/**
 * Insert、Delete、Replace
 *
 * https://www.geeksforgeeks.org/edit-distance-dp-5/
 *
 * @author zk
 */
@LeetCode("72")
@Hard
public class EditDistance {

    public static void main(String[] args) {
        EditDistance editDistance = new EditDistance();
        int minDistance = editDistance.minDistance("horse", "ros");

        Utils.println(minDistance);
    }

    public int minDistance(String word1, String word2) {
        // ==============================
        // 增加缓存层
        // ==============================
        int[][] cacheLayer = new int[word1.length() + 1][word2.length() + 1];
        Utils.fill(cacheLayer, -1);

        return helper(word1, 0, word2, 0, cacheLayer);
    }

    private int helper(String word1, int i, String word2, int j, int[][] cacheLayer /** 增加缓存层 **/) {
        // ==============================
        // 缓存层已有
        // ==============================
        if (cacheLayer[i][j] != -1) {
            return cacheLayer[i][j];
        }

        if (i >= word1.length()) {
            // =========================================================
            // word1 走到头
            // word1 增加 (word2.length() - j) 个字符，就会与 word2 相同了
            // =========================================================
            return cacheLayer[i][j] = (word2.length() - j);
        } else if (j >= word2.length()) {
            // =========================================================
            // word2 走到头
            // word1 删除 (word1.length() - i) 个字符，就会与 word2 相同了
            // =========================================================
            return cacheLayer[i][j] = (word1.length() - i);
        }

        // =========================================================
        // 字符相同，继续对比下一位
        // =========================================================
        if (word1.charAt(i) == word2.charAt(j)) {
            return cacheLayer[i][j] = (helper(word1, i + 1, word2, j + 1, cacheLayer));
        } else {
            // =========================================================
            // word1 删除
            // word1 增加
            // word1 替换 word2
            // =========================================================
            int removeDistance = helper(word1, i + 1, word2, j, cacheLayer) + 1;
            int insertDistance = helper(word1, i, word2, j + 1, cacheLayer) + 1;
            int replaceDistance = helper(word1, i + 1, word2, j + 1, cacheLayer) + 1;

            return cacheLayer[i][j] = Math.min(removeDistance, Math.min(insertDistance, replaceDistance));
        }
    }

}